//给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。 
//
// 请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。 
//
// 你可以假设 nums1 和 nums2 不会同时为空。 
//
// 示例 1: 
//
// nums1 = [1, 3]
//nums2 = [2]
//
//则中位数是 2.0
// 
//
// 示例 2: 
//
// nums1 = [1, 2]
//nums2 = [3, 4]
//
//则中位数是 (2 + 3)/2 = 2.5
// 
// Related Topics 数组 二分查找 分治算法


package leetcode.editor.cn;

import java.util.Arrays;

public class P4MedianOfTwoSortedArrays {
    public static void main(String[] args) {
        Solution solution = new P4MedianOfTwoSortedArrays().new Solution();
        //TO TEST
        double medianSortedArrays = solution.findMedianSortedArrays(new int[]{1, 2, 3}, new int[]{3,4,5,6,7});
        System.out.println(medianSortedArrays);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int m = nums1.length;
            int n = nums2.length;
            if ((m + n) % 2 == 0) {
                return (findKth(nums1, nums2, (m + n) / 2) + findKth(nums1, nums2, (m + n + 2) / 2)) / 2.0;
            } else {//奇数
                return findKth(nums1, nums2, (m + n + 1) / 2);
            }
        }

        public int findKth(int[] nums1, int[] nums2, int k) {
            int length1 = nums1.length;
            int length2 = nums2.length;
            if (length1 == 0) {
                return nums2[k - 1];
            } else if (length2 == 0) {
                return nums1[k - 1];
            }
            //剩余
            int s = k;
            //起始
            int t1 = 0;
            int t2 = 0;
            for (;;) {
                if (t1 >= length1 ) {
                    return nums2[k - length1 - 1];
                } else if (t2 >= length2 ) {
                    return nums1[k - length2 - 1];
                }
                if (s == 1) {
                    return Math.min(nums1[t1],nums2[t2]);
                }
                int j = s / 2;
                int c1 = t1 + j - 1;
                int c2 = t2 + j - 1;

                int n1 = c1 < length1 ? nums1[c1]:Integer.MAX_VALUE;
                int n2 = c2 < length2 ? nums2[c2]:Integer.MAX_VALUE;
                if (n1 > n2) {
                    t2 = c2 + 1;
                } else {
                    t1 = c1 + 1;
                }
                s -= j;
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}